翻訳と辞書 Words near each other ・ Resource (biology) ・ Resolution independence ・ Resolution inference ・ Resolution Island ・ Resolution Island (New Zealand) ・ Resolution Island (Nunavut) ・ Resolution of Sarajevo Muslims ・ Resolution of singularities ・ Resolution of the Comintern on the Macedonian Question ・ Resolution of the Dreyfus Affair ・ Resolution on Taiwan's Future ・ Resolution Party ・ Resolution plc ・ Resolution Point ・ Resolution proof compression by splitting ・ Resolution proof reduction via local context rewriting ・ Resolution Rupes ・ Resolution Subglacial Highlands ・ Resolution Tour ・ Resolution Trust Corporation ・ Resolution, U.S. Virgin Islands ・ Resolution-class submarine ・ Resolutions (album) ・ Resolutions of the Flemish Parliament of 1999 ・ Resolutions of the United Church of Christ ・ Resolv.conf ・ Resolvability criterion ・ Resolvable space ・ Resolvconf ・ Resolve Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Resolution proof reduction via local context rewriting ： ウィキペディア英語版 Resolution proof reduction via local context rewriting In proof theory, an area of mathematical logic, resolution proof reduction via local context rewriting is a technique for resolution proof reduction via local context rewriting.〔Simone, S.F. ; Brutomesso, R. ; Sharygina, N. "An Efficient and Flexible Approach to Resolution Proof Reduction". 6th Haifa Verification Conference, 2010.〕 This proof compression method was presented as an algorithm named ''ReduceAndReconstruct'', that operates as a post-processing of resolution proofs. ReduceAndReconstruct is based on a set of local proof rewriting rules that transform a subproof into an equivalent or stronger one.〔 Each rule is defined to match a specific context. A context〔 involves two pivots ($p$ and $q$) and five clauses ($\backslash alpha$, $\backslash beta$, $\backslash gamma$, $\backslash delta$ and $\backslash eta$). The structure of a context is shown in (). Note that this implies that $p$ is contained in $\backslash beta$ and $\backslash gamma$ (with opposite polarity) and $q$ is contained in $\backslash delta$ and $\backslash alpha$ (also with opposite polarity). The table below shows the rewriting rules proposed by Simone ''et al.''.〔 The idea of the algorithm is to reduce proof size by opportunistically applying these rules. \, \operatorname(s) \qquad \overline E} \, \operatorname(t) \Rightarrow \cfrac\, \operatorname(t) \qquad \cfrac tD}\, \operatorname(t)} \, \operatorname(s) |- | Case A2: $s\; \backslash notin\; \backslash alpha,\; t\; \backslash notin\; \backslash gamma$ || $\backslash cfrac\; \backslash ,\; \backslash operatorname(s)\; \backslash qquad\; \backslash overline\; E\}\; \backslash ,\; \backslash operatorname(t)\; \backslash Rightarrow$ \cfrac \, \operatorname(t) \qquad \overline D} \, \operatorname(s) |- | Case B1: $s\; \backslash in\; \backslash alpha,\; t\; \backslash in\; \backslash gamma$ || $\backslash cfrac\; \backslash ,\; \backslash operatorname(s)\; \backslash qquad\; s\; \backslash overline\; E\}\; \backslash ,\; \backslash operatorname(t)\; \backslash Rightarrow$ \cfrac\, \operatorname(t) |- | Case B2: $s\; \backslash in\; \backslash alpha,\; t\; \backslash notin\; \backslash gamma$ || $\backslash cfrac\; \backslash ,\; \backslash operatorname(s)\; \backslash qquad\; s\; \backslash overline\; E\}\; \backslash ,\; \backslash operatorname(t)\; \backslash Rightarrow$ \cfrac \, \operatorname(t) \qquad \overline D} \, \operatorname(s) |- | Case B3: $\backslash overline\; \backslash in\; \backslash alpha,\; t\; \backslash notin\; \backslash gamma$ || $\backslash cfrac\; \backslash ,\; \backslash operatorname(s)\; \backslash qquad\; \backslash overline\; \backslash overline\; E\}\; \backslash ,\; \backslash operatorname(t)\; \backslash Rightarrow$ \overline D |- | Case A1' || $\backslash cfrac\; \backslash ,\; \backslash operatorname(s)\; \backslash qquad\; \backslash overline\; E\}\; \backslash ,\; \backslash operatorname(t)\; \backslash Leftarrow$ \cfrac\, \operatorname(t) \qquad \cfrac tD}\, \operatorname(t)} \, \operatorname(s) |- | Case B2': $t\; \backslash notin\; \backslash gamma$ || $\backslash cfrac\; \backslash ,\; \backslash operatorname(s)\; \backslash qquad\; s\; \backslash overline\; E\}\; \backslash ,\; \backslash operatorname(t)\; \backslash Rightarrow$ \cfrac\, \operatorname(t) |} The first five rules were introduced in an earlier paper.〔Bruttomesso, R. ; Rollini, S. ; Sharygina, N.; Tsitovich, A. "Flexible Interpolation with Local Proof Transformations". The International Conference on Computer-Aided Design, 2010.〕 In addition: * Rule A2 does not perform any reduction on its own. However, it is still useful, because of its "shuffling" effect that can create new opportunities for applying the other rules; * Rule A1 is not used in practice, because it may increase proof size; * Rules B1, B2, B2' and B3 are directly responsible for the reduction, as they produce a transformed root clause stronger than the original one; * The application of a B rule may lead to an illegal proof (see the example below), as some literals missing in the transformed root clause may be involved in another resolution step along the path to the proof root. Therefore, the algorithm also has to "reconstruct" a legal proof when this happen. The following example〔 shows a situation where the proof becomes illegal after the application of B2' rule: }} \overline}\, q}\, p \qquad \overline s}\, o |}} Applying rule B2' to the highlighted context: } \overline}\, q}\, p \qquad \overline s}\, o |}} The proof is now illegal because the literal $o$ is missing from the transformed root clause. To reconstruct the proof, one can remove $o$ together with the last resolution step (that is now redundant). The final result is the following legal (and stronger) proof: \, q \qquad \cfrac}\, q}\, p |}} A further reduction of this proof by applying rule A2 to create a new opportunity to apply rule B2'.〔 There are usually a huge number of contexts where rule A2 may be applied, so an exhaustive approach is not feasible in general. One proposal〔 is to execute ReduceAndReconstruct as a loop with two termination criteria: number of iterations and a timeout (what is reached first). The pseudocode〔 below shows this. 1 function ReduceAndReconstruct(''$\backslash pi$'' ''/ * a proof */'', ''timelimit'', ''maxIterations''): 2 for i = 1 to ''maxIterations'' do 3 ReduceAndReconstructLoop(); 4 if ''time'' > ''timelimit'' then ''// timeout'' 5 break; 6 end for 7 end function ReduceAndReconstruct uses the function ReduceAndReconstructLoop, which is specified below. The first part of the algorithm does a topological ordering of the resolution graph (considering that edges goes from antecedentes to resolvents). This is done to ensure that each node is visited after its antecedents (this way, broken resolution steps are always found and fixed).〔 1 function ReduceAndReconstructLoop(''$\backslash pi$'' ''/ * a proof */''): 2 ''TS'' = TopologicalSorting($\backslash pi$); 3 for each node $n$ in ''TS'' 4 if $n$ is not a leaf 5 if ''$n\_\backslash text\; \backslash in\; n\_\backslash text^\backslash text$ and $\backslash overline^\backslash text$'' then 6 $n\_\backslash text$ = Resolution($n\_\backslash text^\backslash text$, $n\_\backslash text^\backslash text$); 7 Determine left context of $n$, if any; 8 Determine right context of $n$, if any; 9 Heuristically choose one context (if any) and apply the corresponding rule; 10 else if ''$n\_\backslash text\; \backslash notin\; n\_\backslash text^\backslash text$ and $\backslash overline^\backslash text$'' then 11 Substitute $n$ with $n^\backslash text$; 12 else if ''$n\_\backslash text\; \backslash in\; n\_\backslash text^\backslash text$ and $\backslash overline^\backslash text$'' then 13 Substitute $n$ with $n^\backslash text$; 14 else if ''$n\_\backslash text\; \backslash notin\; n\_\backslash text^\backslash text$ and $\backslash overline^\backslash text$'' then 15 Heuristically choose an antecedent $n^\backslash text$ or $n^\backslash text$; 16 Substitute $n$ with $n^\backslash text$ or $n^\backslash text$; 17 end for 18 end function If the input proof is not a tree (in general, resolution graphs are directed acyclic graphs), then the clause $\backslash delta$ of a context may be involved in more than one resolution step. In this case, to ensure that an application of a rewriting rule is not going to interfere with other resolution steps, a safe solution is to create a copy of the node represented by clause $\backslash delta$.〔 This solution increases proof size and some caution is needed when doing this. The heuristic for rule selection is important to achieve a good compression performance. Simone ''et al.'' 〔 use the following order of preference for the rules (if applicable to the given context): B2 > B3 > > A1' > A2 (X > Y means that X is preferred over Y). Experiments have shown that ReduceAndReconstruct alone has a worse compression/time ratio than the algorithm RecyclePivots.〔Bar-Ilan, O. ; Fuhrmann, O. ; Hoory, S. ; Shacham, O. ; Strichman, O. "Linear-Time Reductions of Resolution Proofs". HVC, 2008.〕 However, while RecyclePivots can be applied only once to a proof, ReduceAndReconstruct may be applied multiple times to produce a better compression. An attempt to combine ReduceAndReconstruct and RecyclePivots algorithms has led to good results.〔 ==Notes== 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Resolution proof reduction via local context rewriting」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.